package 链表高频题和必备技巧;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
public class Code04_PalindromeLinkedList {

    public class ListNode{
        int val;
        ListNode next;
    }

    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        // 找中点
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 现在中点就是slow，从中点开始往后的节点逆序
        ListNode pre = slow;
        ListNode cur = pre.next;
        ListNode next = null;
        pre.next = null;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 上面的过程已经把链表调整成从左右两侧往中间指
        //                null
        //                  ↑
        // head -> ... -> slow <- ... <- pre
        ListNode left = head;
        ListNode right = pre;
        Boolean ans = true;
        while(left != null && right.next != null){
            if(left.val != right.val){
                ans = false;
                break;
            }
            left = left.next;
            right = right.next;
        }
        // 本着不坑的原则，把链表调整回原来的样子再返回判断结果
        cur = pre.next;
        pre.next = null;
        next = null;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return ans;
    }
}
